#define DEBUG
#include <cstdio>
#include <cstring>
#define MODS 258280327
#define MAXLENM 302

using namespace std;

int max(int a, int b) {
  return a>b ? a : b;
}

int cmp(int *a, int *b) {
  if (a[0]<b[0]) {
    return -1;
  } else if (a[0]>b[0]){
    return 1;
  } else {
    for (int i=a[0]; i>0; i--) {
      if (a[i]<b[i]) {
	return -1;
      } else if (a[i]>b[i]) {
	return 1;
      }
    }
    return 0;
  }
}

void add(int *a, int *b, int *c) {
  int len=max(a[0], b[0]);
  c[1] = 0;
  for (int i=1; i<=len; i++) {
    if (a[0]>=i) {
      c[i] += a[i];
    }
    if (b[0]>=i) {
      c[i] += b[i];
    }
    c[i+1] = c[i]/10;
    c[i] = c[i]%10;
  }
  c[0] = c[len+1] ? len+1 : len;
}

void dec(int *a, int *b, int *c) {
  c[1] = 0;
  for (int i=1; i<=a[0]; i++) {
    c[i] += a[i];
    if (b[0]>=i) {
      c[i] -= b[i];
    }
    if (c[i]<0) {
      c[i] += 10;
      c[i+1] = -1;
    } else {
      c[i+1] = 0;
    }
    if (c[i]>0) {
      c[0] = i;
    }
  }
}

long long mod(int *a, int b) {
  long long ret=0;
  for (int i=a[0]; i>0; i--) {
    ret = (ret*10+a[i])%b;
  }
  return ret;
}

int main() {
#ifdef DEBUG
  freopen("4213.in", "r", stdin);
  freopen("4213.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    static char s[MAXLENM+1];
    static int m[MAXLENM+1];
    int n;
    scanf("%d %s", &n, s);
    m[0] = strlen(s);
    for (int i=0; i<m[0]; i++) {
      m[m[0]-i] = s[i]-'0';
    }

    static int slen[3][MAXLENM+1], temp[MAXLENM+1], one[MAXLENM+1];
    one[0] = one[1] = slen[1][0] = slen[1][1] = slen[2][0] = slen[2][1] = 1;
    add(m, one, temp);
    if (m[0]==1 && m[1]==1) {
      printf("0\n");
      continue;
    }
    int i;
    for (i=3; i<=n; i++) {
      add(slen[(i-2)%3], slen[(i-1)%3], slen[i%3]);
      if (cmp(slen[i%3], temp)>0) {
	break;
      }
    }
    dec(m, slen[(i-2)%3], slen[i%3]);
    printf("%lld\n", mod(slen[i%3], MODS));
  }

  fcloseall();
  return 0;
}
